package com.sicheng.datastruct.tree.huffman.huffmantree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.ToString;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/10 8:32
 */
public class HoffmanTree {
    public static void main(String[] args) {

        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node root = initHoffmanTree(arr);
        preOrder(root);

    }

    //前序遍历哈夫曼树
    public static void preOrder(Node root) {
        if (root == null)
            return;

        root.preOrder(root);
    }

    public static Node initHoffmanTree(int[] arr) {

        if (arr == null || arr.length < 1) {
            return null;
        }

        List<Node> nodes = Arrays
                .stream(arr)
                .boxed()
                .map(Node::new)
                .collect(Collectors.toList());

        while (nodes.size() > 1) {
            nodes.sort((Comparator.comparingInt(Node::getValue)));

            Node left = nodes.get(0);
            Node right = nodes.get(1);

            Node parent = new Node(left.value + right.value);
            parent.setLeft(left);
            parent.setRight(right);

            nodes.remove(left);
            nodes.remove(right);

            nodes.add(parent);
        }

        return nodes.get(0);

    }


    @Data
    @NoArgsConstructor
    @AllArgsConstructor
    @ToString(of = "value")
    static class Node {
        private int value;
        private Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
        }


        private void preOrder(Node root) {
            System.out.println(root);

            if (root.getLeft() != null)
                preOrder(root.getLeft());

            if (root.getRight() != null)
                preOrder(root.getRight());
        }
    }
}
